package com.topcoder.srm150;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class RoboCourier {
	private int[] dx = new int[]{0, 1,  1,  0, -1, -1};
	private int[] dy = new int[]{2, 1, -1, -2, -1,  1};
	
	private PriorityQueue<Vertex>		pq;
	private HashSet<String>				edges;
	
	public int timeToDeliver(String[] path) {
		edges = new HashSet<String>();
		int direction = 0;
		int x1=0;
		int y1=0;
		
		for (String segment : path) {
			char[] cs = segment.toCharArray();
			for (char c : cs) {
				if (c == 'F') {
					int x2 = x1 + dx[direction];
					int y2 = y1 + dy[direction];
					edges.add(x1 + " " + y1 + " " + x2 + " " + y2);
					edges.add(x2 + " " + y2 + " " + x1 + " " + y1);
					x1 = x2;
					y1 = y2;
				}
				else if (c == 'L') {
					direction = (direction + 5) % 6;
				}
				else {
					direction = (direction + 1) % 6;
				}
			}
		}
		
		pq = new PriorityQueue<Vertex>(10, new Comparator<Vertex>(){
			public int compare(Vertex a, Vertex b) {
				return a.cost - b.cost;
			}
		});
		pq.add(new Vertex(0, 0, 0, 0, 0));
		pq.add(new Vertex(0, 0, 1, 3, 0));
		pq.add(new Vertex(0, 0, 2, 6, 0));
		pq.add(new Vertex(0, 0, 3, 9, 0));
		pq.add(new Vertex(0, 0, 4, 6, 0));
		pq.add(new Vertex(0, 0, 5, 3, 0));
		
		while (!pq.isEmpty()) {
			Vertex v = pq.remove();
			if (v.x == x1 && v.y == y1) return v.cost;
			
			for (int i=0; i<6; i++) {
				int newDirection = (v.direction + i) % 6;
				int x2 = v.x + dx[newDirection];
				int y2 = v.y + dy[newDirection];
				if (!isScouted(v, x2, y2)) continue;
				
				update(x2, y2, newDirection, v);
			}
		}
		
		return -1;
	}
	
	private void update(int x, int y, int direction, Vertex v) {
		int cost = v.cost;
		if (direction!=v.direction) {
			int rotate = (direction - v.direction + 6) % 6;
			cost += 4 + (rotate<=3? rotate*3 : (6-rotate)*3);
		}
		else {
			cost += v.fCount >= 2? 2 : 4;
		}
		
		int fCount = direction==v.direction? v.fCount+1 : 1;
		for (Vertex visited : pq) {
			if (visited.x == x && visited.y == y && visited.direction == direction) {
				if (cost < visited.cost) {
					visited.cost = cost;
					visited.fCount = fCount;
				}
				else if (cost == visited.cost && fCount > visited.fCount) {
					visited.fCount = fCount;
				}
				return;
			}
		}
		
		pq.add(new Vertex(x, y, direction, cost, fCount));
	}
	
	private boolean isScouted(Vertex v, int x, int y) {
		String s1 = v.x + " " + v.y + " " + x + " " + y;
		return edges.contains(s1);
	}
	
	private class Vertex {
		int x, y, direction, cost, fCount;
		
		public Vertex(int x, int y, int direction, int cost, int fCount) {
			this.x = x;
			this.y = y;
			this.direction = direction;
			this.cost = cost;
			this.fCount = fCount;
		}
	}
}
